package LeetCode._02算法基础.day15动态规划;

/**
 * @author 挚爱之夕
 * @version 中等
 * @implSpec 一条包含字母A-Z 的消息通过以下映射进行了 编码 ：
 * 'A' -> "1"
 * 'B' -> "2"
 * ...
 * 'Z' -> "26"
 * 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
 * "AAJF" ，将消息分组为 (1 1 10 6)
 * "KJF" ，将消息分组为 (11 10 6)
 * 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
 * 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
 * 题目数据保证答案肯定是一个 32 位 的整数。
 * @since 2022 - 09 - 11 - 8:59
 */
public class _91解码方式 {
    public static void main(String[] args) {
        String s = "11106";
        System.out.println(numDecodings(s));
    }
    //动态规划
    public static int numDecodings(String s) {
        if(s.charAt(0) == '0')  //前置为0的情况
            return 0;
        int n = s.length();
        //dp[i] 表示 前 i 个 字符 解码方法的总数
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i = 1; i < n + 1; i++){
            //i - 1 为当前字符索引
            if(s.charAt(i - 1) != '0'){ //将当前单个字符解码：解码方法数等于dp[i - 1]
                dp[i] += dp[i - 1];
            }
            //将 i - 2 和当前 字符映射为一个字符 ： 解码方法数等于 dp[i - 2]
            if(i - 1 > 0 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0')) <= 26){
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
    //优化：降低空间复杂度
    public static int numDecodings1(String s) {
        if(s.charAt(0) == '0')
            return 0;
        //dp[i - 2] dp[i - 1] dp[i]
        int a = 0, b = 1, c = 0;

        for(int i = 1; i <= s.length(); i++){
            int index = i - 1;
            c = 0;
            if(s.charAt(index) != '0'){
                c += b;
            }

            if(index > 0 && s.charAt(index - 1) != '0' && ((s.charAt(index - 1) - '0') * 10 + (s.charAt(index) - '0')) <= 26){
                c += a;
            }
            a = b;
            b = c;
        }
        return c;
    }
}
